public class Sort {
    public static void insertSrt(int[] array){
        for (int i = 0; i <array.length; i++) {
            int tmp=array[i];
            int j=i-1;
            for ( ;j >=0; j--) {
                if (array[j]>tmp){
                    array[j+1]=array[j];
                }
                else {
                    break;
                }

            }
            array[j+1]=tmp;
        }
    }
    //插入排序
    //希尔排序
    public static void shellSort(int[] array) {
        int gap = array.length;
        while (gap > 1) {
            gap /= 2;
            shell(array,gap);
        }
    }


    public static void shell(int[] array,int gap) {
        for (int i = gap; i < array.length; i++) {
            int tmp = array[i];
            int j = i-gap;
            for (; j >= 0 ; j-=gap) {
                //这里加不加等号  和稳定有关系
                // 但是：本身就是一个稳定的排序 可以实现为不稳定的排序
                // 但是 本身就是一个不稳定的排序 是不可能变成一个稳定的排序的
                if(array[j] > tmp) {
                    array[j+gap] = array[j];
                }else {
                    //array[j+1] = tmp;
                    break;
                }
            }
            array[j+gap] = tmp;
        }
    }
    private static void swap(int[] array,int i,int j){
        int tmp=array[i];
        array[i]=array[j];
        array[j]=tmp;
    }
    //选择排序

    public static void selectSort(int[] array){
        for (int i = 0; i <array.length; i++) {
            int minIndex=i;
            for (int j = i+1; j < array.length; j++) {
                if (array[j]<array[minIndex]){
                    minIndex=j;

                }
            }
            swap(array,i,minIndex);
        }
    }
    private static void creareHeap(int[]array){
        for (int parent = (array.length-1-1)/2; parent >=0 ; parent++) {
            siftDown(array,parent,array.length);
        }
    }
    private static void siftDown(int[] array,int parent,int length){
        int child=2*parent+1;
        while (child<length){
            if (child + 1 < length && array[child] < array[child+1]){
                    child++;
            }
            if (array[child]>array[parent]){
                swap(array,child,parent);
                parent=child;
                child=2*parent+1;

            }
            else {
                break;
            }
        }
    }
    public static void heapsort(int[] array){
        creareHeap(array);
        int end=array.length-1;

    }

}


